package leetcode_tag.树;

import leetcode.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class LeetCode102 {

    List<List<Integer>> result = new ArrayList<>();


    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null)
            return ans;
        List<TreeNode> currentLevel = new ArrayList<>();
        List<TreeNode> nextLevel = new ArrayList<>();
        currentLevel.add(root);

        while (currentLevel.size() != 0) {
            List<Integer> tmpResult = new ArrayList<>();
            for (TreeNode node : currentLevel) {
                if (node != null) {
                    tmpResult.add(node.val);
                    if (node.left != null)
                        nextLevel.add(node.left);
                    if (node.right != null)
                        nextLevel.add(node.right);
                }
            }
            currentLevel = nextLevel;
            nextLevel = new ArrayList<>();
            ans.add(tmpResult);
        }
        return ans;
    }

    // 广度优先遍历
    public List<List<Integer>> levelOrder1(TreeNode root) {
        helper(root, 0);
        return result;
    }

    private void helper(TreeNode node, int level) {
        if (node != null) {
            while (level >= result.size())
                result.add(new ArrayList<>());
            result.get(level).add(node.val);
            helper(node.left, level + 1);
            helper(node.right, level + 1);
        }
    }
}
